Accelerated Cyclic Reduction: A Distributed-Memory Fast Solver for Structured Linear Systems

摘要

We present Accelerated Cyclic Reduction (ACR), a distributed-memory fastdirect solver for rank-compressible block tridiagonal linear systems arisingfrom the discretization of elliptic operators, developed here for threedimensions. Algorithmic synergies between Cyclic Reduction and hierarchicalmatrix arithmetic operations result in a solver that has $O(k~N \log N~(\log N+ k^2))$ arithmetic complexity and $O(k~N \log N)$ memory footprint, where $N$is the number of degrees of freedom and $k$ is the rank of a typicaloff-diagonal block, and which exhibits substantial concurrency. We provide abaseline for performance and applicability by comparing with the multifrontalmethod where hierarchical semi-separable matrices are used for compressing thefronts, and with algebraic multigrid. Over a set of large-scale ellipticsystems with features of nonsymmetry and indefiniteness, the robustness of thedirect solvers extends beyond that of the multigrid solver, and relative to themultifrontal approach ACR has lower or comparable execution time and memoryfootprint. ACR exhibits good strong and weak scaling in a distributed contextand, as with any direct solver, is advantageous for problems that require thesolution of multiple right-hand sides.